package acwing;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q004_红与黑 {
    static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // 计数是包括初始位置的瓷砖
    public static int func(String[][] mat) {
        // 记录人的位置
        int x = 0;
        int y = 0;
        // 扫描瓷砖数组 确定人的位置
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if ("@".equals(mat[i][j])) {
                    x = i;
                    y = j;
                    break;
                }
            }
        }
        int res = dfs(mat,x,y);
        return res;
    }

    public static int dfs(String[][] mat,int x, int y) {
        int res = 0;
        Deque<Pair> deque = new ArrayDeque<>(); // 采用队列模拟
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        deque.offer(new Pair(x,y)); // 初始化队列
        while (!deque.isEmpty()) {
            Pair pair = deque.poll();
            res++;
            for (int i = 0; i < 4; i++) {
                int a = pair.x + dx[i];
                int b = pair.y + dy[i];
                if (a < 0 || a >= mat.length || b < 0 || b >= mat[0].length || !".".equals(mat[a][b])) {
                    continue;
                }
                mat[a][b] = "#";
                deque.offer(new Pair(a,b));
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String[][] mat = {
                {".",".",".",".","#","."},
                {".",".",".",".",".","#"},
                {".",".",".",".",".","."},
                {".",".",".",".",".","."},
                {".",".",".",".",".","."},
                {".",".",".",".",".","."},
                {".",".",".",".",".","."},
                {".",".",".",".",".","."},
                {"#","@",".",".",".","#"},
                {".","#",".",".","#","."},
                {".","#",".",".","#","."},
        };
        System.out.println(func(mat));
        /**
         * [[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]
         */

    }

}



